<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Exercise 4.47: Maximum determinant PSD matrix completion</title>
<link rel="canonical" href="/Users/mcgrant/Projects/CVX/examples/cvxbook/Ch04_cvx_opt_probs/html/max_det_psd_completion.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Exercise 4.47: Maximum determinant PSD matrix completion</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Almir Mutapcic - Jan 2006</span>
<span class="comment">%</span>
<span class="comment">% Given a symmetric matrix A in R^(n-by-n) with some entries unspecified</span>
<span class="comment">% we find its completion such that A is positive semidefinite and</span>
<span class="comment">% it has a maximum determinant out of all possible completions.</span>
<span class="comment">% This problem can be formulated as a log det (and det_rootn) problem.</span>
<span class="comment">%</span>
<span class="comment">% This is a numerical instance of the specified book exercise.</span>

<span class="comment">% problem size</span>
n = 4;

<span class="comment">% create and solve the problem</span>
cvx_begin <span class="string">sdp</span>
  <span class="comment">% A is a PSD symmetric matrix (n-by-n)</span>
  variable <span class="string">A(n,n)</span> <span class="string">symmetric</span>;
  A &gt;= 0;

  <span class="comment">% constrained matrix entries.</span>
  A(1,1) == 3;
  A(2,2) == 2;
  A(3,3) == 1;
  A(4,4) == 5;
  <span class="comment">% Note that because A is symmetric, these off-diagonal</span>
  <span class="comment">% constraints affect the corresponding element on the</span>
  <span class="comment">% opposite side of the diagonal.</span>
  A(1,2) == .5;
  A(1,4) == .25;
  A(2,3) == .75;

  <span class="comment">% find the solution to the problem</span>
  maximize( log_det( A ) )
  <span class="comment">% maximize( det_rootn( A ) )</span>
cvx_end

<span class="comment">% display solution</span>
disp([<span class="string">'Matrix A with maximum determinant ('</span> num2str(det(A)) <span class="string">') is:'</span>])
A
disp([<span class="string">'Its eigenvalues are:'</span>])
eigs = eig(A)
</pre>
<a id="output"></a>
<pre class="codeoutput">
 
Successive approximation method to be employed.
   For improved efficiency, SDPT3 is solving the dual problem.
   SDPT3 will be called several times to refine the solution.
   Original size: 59 variables, 18 equality constraints
   1 exponentials add 8 variables, 5 equality constraints
-----------------------------------------------------------------
 Cones  |             Errors              |
Mov/Act | Centering  Exp cone   Poly cone | Status
--------+---------------------------------+---------
  1/  1 | 2.753e-01  4.915e-03  0.000e+00 | Solved
  1/  1 | 3.497e-02  8.018e-05  0.000e+00 | Solved
  1/  1 | 4.030e-03  1.064e-06  0.000e+00 | Solved
  0/  1 | 4.704e-04  1.396e-08  0.000e+00 | Solved
-----------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +3.02422
 
Matrix A with maximum determinant (20.578) is:

A =

    3.0000    0.5000    0.1875    0.2500
    0.5000    2.0000    0.7500    0.0417
    0.1875    0.7500    1.0000    0.0156
    0.2500    0.0417    0.0156    5.0000

Its eigenvalues are:

eigs =

    0.5964
    2.0908
    3.2773
    5.0355

</pre>
</div>
</body>
</html>